package offer;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @Author Elephas
 * @Date 2022/1/28
 **/
@FunctionalInterface
public interface LevelOrderBottom {
    List<List<Integer>> levelOrderBottom(TreeNode root);
}
class LevelOrderBottomImpl1 implements LevelOrderBottom{

    @Override
    public List<List<Integer>> levelOrderBottom(TreeNode root) {

        // List<List<Integer>> ans = new ArrayList<>();
        // 使用链表可以每次插入新的 List 时，直接头插，减少时间开销
        List<List<Integer>> ans = new LinkedList<>();
        if(root == null){
            return ans;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            int currentSize = queue.size();
            List<Integer> temp = new ArrayList<>();
            ans.add(0,temp);
            for (int i = 0; i < currentSize; i++) {
                TreeNode tempNode = queue.poll();
                temp.add(tempNode.val);
                if(tempNode.left != null){
                    queue.add(tempNode.left);
                }
                if(tempNode.right != null){
                    queue.add(tempNode.right);
                }
            }
        }
        return ans;
    }

}
